1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a method and system for handling the output queuing of received packets in a switching hub in a packet-switching network.
2. Description of Related Art
A computer network system is composed of a number of building blocks, including hubs, bridges, routers, network adapters, terminals, servers, transmission media connectors, network management programs, and so on. A hub is a device that joins communication lines at a central location to provide a common connection to all devices on the network. Various types of hubs are provided in a network, including, for example, standalone repeating hubs, stackable hubs, and switching hubs. A switching hub includes a plurality of ports and is capable of performing the so-called store-and-forward function, which stores the packets (or called frames) received at one port thereof temporarily therein and then outputs the stored packets from designated port or ports thereof so as to forward them to their destinations. A packet is typically 64 bytes to 1518 bytes in length. In Ethernet, there are three types of packets: broadcast packets, multicast packets, and unicast packets. When a switching hub receives a broadcast packet at one port thereof, the received broadcast packet will be subsequently outputted from all the other ports; when a multicast packet is received, it will be subsequently outputted only from some designated ports; and when a unicast packet is received, it will be subsequently outputted solely from one designated port. Presently, a switching hub typically includes 16 ports, with each port having a data rate of 100 MBps (megabyte per second). The conventional switching hub is describing as follows.
FIG. 1 is a schematic diagram showing the core architecture of a conventional switching hub. As shown, the switching hub includes a switching IC (integrated circuit) or a control IC 100, an SRAM (static random-access memory) unit 110, and a memory, such as an SDRAM (synchronous dynamic random-access memory) unit 120. The switching IC 100 contains the control circuits used to control the store-and-forward function for the received packets.
Referring also to FIG. 2, the SRAM unit 110 includes a first storage area 112 for storing a forward table, a second storage area 114 for storing the available link nodes of free lists (hereinafter referred to a free-list link node set), and a third storage area 116 for storing an attribute-entry list. The forward table 112 is used to register the source address and destination port number of each received packet; the free-list link node set 114 is used to store all the available free-list link nodes in the switching hub, each stored free-list link node being indicated by the reference numeral 114a; and the attribute-entry list 116 is used to stored a number of attribute entries, each stored attribute entry being indicated by the reference numeral 116a. Further, each port of the switching hub is associated with an output queue for sequencing those packets that are to be outputted from this associated port.
FIG. 3A is a schematic diagram used to depict the data structure of each output queue, here designated by the reference numeral 130. Each time when a packet is received and intended to be outputted from a certain designated port, the switching IC 100 will responsively retrieve a free-list link node 114a from the free-list link node set 114 in the SRAM unit 110 and then assign the retrieved free-list link node 114a to the output queue 130 of the designated port. FIG. 3A shows the case of having three link nodes (herein indicated by the reference numeral 114axe2x80x2) assigned to the output queue 130. Further, each output queue 130 includes an output-queue head H and an output-queue tail T, which are respectively pointed to the first and last link nodes in the output queue 130.
Further, FIG. 3B shows the format of each link node 114axe2x80x2 in the output queue 130 of FIG. 3A. As shown, in this preferred embodiment, each link node 114axe2x80x2 is 64 bits in length, wherein Bit 0 is used as a drop flag indicative of whether this link node 114axe2x80x2 is being used or unused; Bits 1 to 16 are collectively used to serve as a pointer indicative of the address of the next link node; Bit 17 is used to indicate the type of the packet that is pointed by this link node 114axe2x80x2; and Bits 18 to 33 are collectively used to serve as a pointer indicative of the address of the packet buffer where the pointed packet is stored.
Referring back to FIGS. 1 and 2, the SDRAM unit 120 is partitioned into a plurality of blocks 122, each having a size of 1.5 KB (kilobyte) and being used as a packet buffer for temporary storage of one of the received packets. Each attribute entry 116a in the attribute-entry list 116 in the SRAM unit 110 is mapped in one-to-one correspondence to one of the packet buffers 122 in the SDRAM unit 120, and is used to indicate whether the corresponding packet has been forwarded or not.
FIG. 3C shows the format of each attribute entry 116a in the attribute-entry list 116 in the SRAM unit 110. As shown, each attribute entry 116a is also 64 bits in length, wherein Bits 0-15 are collectively used as a pointer indicative of the address of the next free-list link node; Bits 16-32 are collectively used as a port mask; and Bits 33-63 are reserved.
The switching hub is designed to handle the received packets in a FIFO (First-In First-Out) manner. To satisfy this requirement, however, the switching hub of FIG. 1 would be considerably inefficient in its store-and-forward operation. This drawback is depicted with the following example. Assume the switching hub of FIG. 1 receives a broadcast packet at one port (for example, Port 0) thereof and subsequently receives a unicast packet at another port (for example, Port 12) thereof, and the received unicast packet is to be outputted from still another port (for example, Port 1) of the switching hub. The operation performed by the switching hub of FIG. 1 to handle this situation is depicted in FIG. 4. As shown, assume the output queue at Port 1 currently contains 6 link nodes U11-U16 for the outputting of six unicast packets; the output queue at Port 2 currently contains 2 link nodes U21-U22 for the outputting of 2 unicast packets; and the output queue at Port 3 currently contains 9 link nodes U31-U39 (in FIG. 4, Port 4 through Port 15 are eliminated for simplification of the drawing and description). When the switching hub receives a broadcast packet at Port 0, the SRAM unit 110 will responsively assign 15 free-list link nodes 114a respectively to the Port 1 through Port 15, thereby forming a broadcast-packet link node B at the end of each output queue, with each broadcast-packet link node B pointing to one of the packet buffers 122 in the SDRAM unit 120 where the received broadcast packet is temporarily stored. The pointed packet buffer is further mapped to one of the attribute entries 116a in the attribute-entry list 116 in the SRAM unit 110. The port-mask portion (Bits 16-32) of each attribute entry 116a is used to indicate whether the associated broadcast packet has been forwarded or not. At the time t2 when a unicast packet is received at Port 12 and is intended to be outputted from Port 1 for forwarding to its destination, the SRAM unit 110 will responsively assign one free-list link node 114a in the SRAM unit 110 to the output queue at Port 1. At t6, Port 1 retrieves the broadcast packet stored in the one of the packet buffers 122 that is pointed by the broadcast-packet link node B. After this, in order to meet the FIFO requirement, Port 1 will output the unicast packet after the outputting of the broadcast packet is completed. After the broadcast packet is outputted from all the other ports, the SRAM unit 110 will relinquish all the associated 15 link nodes and attribute entries.
It can be learned from the foregoing description that it would involve very frequent accesses to the SRAM unit 110 when handling each received broadcast packet. For instance, the operation of assigning the 15 free-list link nodes to the respective output queues at the 15 ports requires a total of 15 accesses to the SRAM unit 110; and subsequently, the enqueuing of these 15 free-list link nodes to the respective output queues further requires a total of 15 accesses to the SRAM unit 110; and still moreover, after the forwarding of the received broadcast packet is completed, the dequeuing of the 15 link nodes from the respective output queues further requires a total of 15 accesses to the SRAM unit 110. Overall, the forwarding of each broadcast packet through the switching hub requires a total of 93 accesses to the SRAM unit 110, which could significantly slow down the system performance.
Moreover, for each broadcast packet, it requires the assignment of 15 free-list link nodes to the respective output queues at all the ports where the broadcast packet is to be outputted. As a result, when a great number of broadcast packets are received, they will take up an enormously large space in the SRAM unit 110; and therefore, it requires the SRAM unit 110 to be large enough in storage capacity so as to be able to handle these broadcast packets. A large memory capacity, however, would considerably increase the implementation cost of the switching hub. Furthermore, the attribute entries and link nodes that are registered in the SRAM unit 110 in response to the received broadcast packets also take up quite a large storage space in the SRAM unit 110. The SRAM unit 110 should therefore large in storage capacity, which further increase the implementation cost of the network system.
It is therefore an object of this invention to provide a method and system for handling the output queuing of received packets in a switching hub in a packet-switching network, which can help reduce the number of accesses to the memory as compared to the prior art, so as to help increase the packet transmission performance.
It is another object of this invention to provide a method and system for handling the output queuing of received packets in a switching hub in a packet-switching network, which can be implemented without having to use an attribute-entry list so that the required memory capacity in the switching hub can be reduced as compared to the prior art to help reduce implementation cost.
It is still another object of this invention to provide a method and system for handling the output queuing of received packets in a switching hub in a packet-switching network, which can be implemented with a smaller memory capacity than the prior art while nevertheless is able to handle the forwarding of a large amount of received broadcast packets.
In accordance with the foregoing and other objects of this invention, a new method and system is provided for handling the output queuing of received packets in a switching hub in a packet-switching network.
By the invention, a broadcast output queue is provided in addition to the output queues at the ports of the switching hub. In response to a received packet, it is checked whether the received packet is a unicast packet or a broadcast output queue; if a unicast packet, the method of the invention assigns a free-list link node to the output queue at the destination port of the received unicast packet, the link node containing a broadcast count indicative of the number of currently received broadcast packets in the switching hub; otherwise, if a broadcast packet, the method of the invention assigns a free-list link node to the broadcast output queue and meanwhile adding one to the broadcast count in each of the last link node in each of the output queues at the ports of the switching hub. Subsequently, it is checked whether the broadcast count in each of the last link node in each of the output queues at the ports of the switching hub; if zero, the unicast packet pointed by the link node is outputted from the designated port; otherwise, if nonzero, the switching hub outputs every broadcast packet indicated by the broadcast count.
The invention further provides a system for use on a switching hub in a packet-switching network for the purpose of handling the output queuing of received packets in the switching hub, the switching hub having a plurality of ports, with each port being associated with an output queue. The system of the invention comprises the following constituent parts: (a) a first memory unit for storing a forward table and a free-list link node set, the forward table being used to register the source address and destination port number of each received packet, and the free-list link node set being used to contain available link nodes of free lists in the switching hub; (b) a second memory unit including a plurality of packet buffers for temporary storage of received packets; (c) a plurality of output queues, each being associated with one of the ports of the switching hub and being used for the sequencing of received packets that are awaiting for outputting from designated ports; (d) a broadcast output queue used for the sequencing of received broadcast packets that are awaiting for outputting from the switching hub; and (e) a switching control unit for controlling the access operations to the first and second memory units and the enqueuing and dequeuing of the output queues and the broadcast output queue; the switching control unit operating in such a manner that when a packet is received, the switching control unit checks whether the received packet is a unicast packet or a broadcast packet; if a unicast packet, the switching control unit retrieves a free-list link node from the first memory unit and then assigns the retrieved link node to the output queue at the destination port of the received unicast packet, the link node further containing a broadcast count indicative of the number of currently received broadcast packets in the switching hub; otherwise, if a broadcast packet, the switching control unit retrieves a free-list link node from the first memory unit and assigns the retrieved link node to the broadcast output queue and meanwhile adding one to the broadcast count in each of the last link node in each of the output queues.
The foregoing method and system of the invention not only allows a reduced number of memory accesses as compared to the prior art, but also requires a low memory capacity to implement. The invention is therefore more efficient in operation and more cost-effective to implement than the prior art.